package main


var minCost int
func maxJump(stones []int) int {
	minCost = 1<<31 - 1
	visited := make([]bool, len(stones))
	backtrack(stones, visited, 1, 0, 0)
	return minCost
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// already at stones[position], make next move
func backtrack(stones []int, visited []bool, direction int, position int, cost int) {
	if direction == -1 && position == 0 {
		// at home
		if cost < minCost {
			minCost = cost
		}
		return
	}
	if position == len(stones) - 1 {
		// hit the end, reverse direction
		direction = -1
	}
	if direction == 1 {
		// move right
		for i := position+1; i < len(stones); i++ {
			if visited[i] {
				continue
			}
			visited[i] = true
			cost2 := max(stones[i] - stones[position], cost)
			backtrack(stones, visited, direction, i, cost2)
			visited[i] = false
		}
	} else {
		// move left
		for i := position-1; i >= 0; i-- {
			if visited[i] {
				continue
			}
			visited[i] = true
			cost2 := max(cost, stones[position] - stones[i])
			backtrack(stones, visited, direction, i, cost2)
			visited[i] = false
		}
	}
}

func maxJump2(stones []int) int {
	ans := stones[1] - stones[0]
	for i := 2; i < len(stones); i++ {
		ans = max(ans, stones[i]-stones[i-2])
	}
	return ans
}

func main() {
	stones := []int{0,2,5,6,7}
	// stones = []int{0,1}
	cost := maxJump(stones)
	println(cost)
}